package 动态规划;

/**
 * https://leetcode.cn/problems/check-if-there-is-a-valid-parentheses-string-path/solution/tian-jia-zhuang-tai-hou-dfscpythonjavago-f287/
 * 先挂个 不错的 题解  链接
 * 这个题  是 如果 有一条 可行的 道路 就 返回     true
 * 那其实  在 网格 中 是由 很多  可行的 道路的 
 *所以   该题 的 变形 就是 直接  求出 有多少 条   合法的  道路 
 * 典型 的 一种  dp  问题 对吧 
 * 先暴力 递归 出来 然后 在   优化成 dp （可能是 三维 dp ） （几维度 dp 并不重要 ）
 * 只要 暴力 递归 能写出来   管你  几 维 dp   都无所谓的 
 * @author I adore you
 *
 */

public class leetcode2267三维dp或者记忆化搜索 {
	
	
	public static void main(String []args) {
	}
	static boolean solution(char grid [][]) {
		int m = grid.length;
		int n = grid[0].length;
		if(grid[0][0] == ')' || grid[m - 1][n - 1] == '(')
			return false;
		return process(grid,0,0,m - 1,n - 1);
	}
	/**
	 * 注意 只能 向下 或者 向右 
	 * 所以  这个  方向数组 就是  int dir [][] = {{0,1},{1,0}}
	 */
	static boolean process(char grid [][] ,int x,int y,int m,int n) {
		if(x > m || y > n)
			return false;
		if(x == m && n == y)
			return true;
		
		return false;
	}
	
	
	
	
	
	
	
	
	
	
	
	
//	public static void main(String []args) {
//		String [][] grid = {{"(",")"},{"(","("}};
//		System.out.println(grid.length);
//		System.out.println(solution(grid));
//	}
//	static boolean solution(String grid [][]) {
//		if(grid[0][0].equals(")"))
//			return false;
//		int m = grid.length;
//		int n = grid[0].length;
//		return process(grid,0,0,m - 1,n - 1);
//	}
//	/**
//	 * 注意 只能 向下 或者 向右 
//	 * 所以  这个  方向数组 就是  int dir [][] = {{0,1},{1,0}}
//	 */
//	static boolean process(String grid [][] ,int x,int y,int m,int n) {
//		if(x > m || y > n)
//			return false;
//		if(x == m && n == y)
//			return true;
//		if(grid[x][y].equals("(") && grid[x + 1][y].equals(")"))
//			return process(grid,x + 1,y,m,n);
//		if(grid[x][y].equals("(") && grid[x][y + 1].equals(")"))
//			return process(grid,x,y + 1,m,n);
//		if(grid[x][y].equals(")") && grid[x + 1][y].equals("("))
//			return process(grid,x + 1,y,m,n);
//		if(grid[x][y].equals(")") && grid[x][y + 1].equals("("))
//			return process(grid,x,y + 1,m,n);
//		return false;
//	}
}
